%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require An undirected or directed graph $G = (V, E)$ that is weighted
  and has no self-loops. The order of $G$ is $n > 0$. A vertex $s \in V$
  from which to start the search. Vertices are numbered from 1 to $n$,
  i.e.~$V = \{1, 2, \dots, n\}$.
\Ensure A list $D$ of distances such that $D[v]$ is the distance of a
  shortest path from $s$ to $v$. A list $P$ of vertex parents such
  that $P[v]$ is the parent of $v$, i.e. $v$ is adjacent from $P[v]$.
%%
%% algorithm body
\State $D \gets [\infty, \infty, \dots, \infty]$\Comment{$n$ copies of $\infty$}
\State $D[s] \gets 0$
\State $P \gets [\,]$
\State $Q \gets V$\Comment{list of nodes to visit}
\While{$\length(Q) > 0$\label{alg:dijkstra_general:while_loop}}
  \State find $v \in Q$ such that $D[v]$ is minimal\label{alg:dijkstra_general:find_vertex_minimal_distance}
  \State $Q \gets \remove(Q, v)$
  \For{\rm each $u \in \adj(v) \cap Q$\label{alg:dijkstra_general:for_loop}}
    \If{$D[u] > D[v] + w(vu)$\label{alg:dijkstra_general:if_relaxation}}
      \State $D[u] \gets D[v] + w(vu)$
      \State $P[u] \gets v$
    \EndIf
  \EndFor
\EndWhile
\State \Return $(D, P)$
\end{algorithmic}
